#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define PAGE_SIZE 4096  ///< 定义页面大小
#define MAX_MEMORY_PAGES 1024  ///< 定义最大允许的内存页数

/**
 * @brief 基数树节点结构体
 * 
 * 包含256个子节点指针数组和一个数据指针。
 */
typedef struct RadixNode {
    struct RadixNode *children[256];  ///< 256个可能的ASCII字符
    char *data;  ///< 存储数据的指针
} RadixNode;

/**
 * @brief 基数树结构体
 * 
 * 包含指向根节点的指针和已使用的内存页计数。
 */
typedef struct {
    RadixNode *root;  ///< 根节点
    size_t used_pages;  ///< 已使用的内存页计数
} RadixTree;

/**
 * @brief 创建新的基数树节点
 * 
 * @return RadixNode* 新创建的基数树节点
 */
RadixNode* create_node() {
    RadixNode *node = (RadixNode *)malloc(sizeof(RadixNode));
    if (!node) {
        fprintf(stderr, "内存分配失败\n");
        exit(EXIT_FAILURE);
    }
    memset(node->children, 0, sizeof(node->children));  ///< 初始化子节点指针为NULL
    node->data = NULL;  ///< 初始化数据指针为NULL
    return node;
}

/**
 * @brief 创建基数树
 * 
 * @return RadixTree* 新创建的基数树
 */
RadixTree* create_tree() {
    RadixTree *tree = (RadixTree *)malloc(sizeof(RadixTree));
    if (!tree) {
        fprintf(stderr, "内存分配失败\n");
        exit(EXIT_FAILURE);
    }
    tree->root = create_node();  ///< 初始化根节点
    tree->used_pages = 0;  ///< 初始化已使用页计数
    return tree;
}

/**
 * @brief 在基数树中插入数据
 * 
 * 如果达到最大内存页数，数据插入会失败。
 * 
 * @param tree 指向基数树的指针
 * @param key 插入数据的键
 * @param data 插入的数据
 */
void insert_data(RadixTree *tree, const char *key, const char *data) {
    if (tree->used_pages >= MAX_MEMORY_PAGES) {  ///< 检查内存页限制
        fprintf(stderr, "Memory limit reached\n");
        return;
    }
    RadixNode *node = tree->root;
    while (*key) {  ///< 遍历密钥的每个字符
        if (!node->children[(unsigned char)*key]) {
            node->children[(unsigned char)*key] = create_node();  ///< 创建新的子节点
        }
        node = node->children[(unsigned char)*key];
        key++;
    }
    if (!node->data) {
        node->data = (char *)malloc(PAGE_SIZE);  ///< 分配内存页
        tree->used_pages++;
    }
    strncpy(node->data, data, PAGE_SIZE);  ///< 复制数据到节点
}

/**
 * @brief 在基数树中搜索数据
 * 
 * @param tree 指向基数树的指针
 * @param key 搜索数据的键
 * @return char* 找到的数据或NULL
 */
char* search_data(RadixTree *tree, const char *key) {
    RadixNode *node = tree->root;
    while (*key && node) {  ///< 遍历密钥的每个字符
        node = node->children[(unsigned char)*key];
        key++;
    }
    return node ? node->data : NULL;  ///< 返回找到的数据或NULL
}

/**
 * @brief 写操作模拟
 * 
 * @param tree 指向基数树的指针
 * @param fn 文件名
 * @param offset 偏移量
 * @param buff 要写入的数据缓冲区
 */
void Mwrite(RadixTree *tree, const char *fn, size_t offset, const char *buff) {
    char key[256];
    snprintf(key, sizeof(key), "%s_%zu", fn, offset);  ///< 构造键值
    insert_data(tree, key, buff);
    printf("Write: File: %s, Offset: %zu, Length: %zu\n", fn, offset, strlen(buff));
}

/**
 * @brief 读操作模拟
 * 
 * @param tree 指向基数树的指针
 * @param fn 文件名
 * @param offset 偏移量
 * @param size 要读取的数据长度
 */
void Mread(RadixTree *tree, const char *fn, size_t offset, size_t size) {
    char key[256];
    snprintf(key, sizeof(key), "%s_%zu", fn, offset);  ///< 构造键值
    char *data = search_data(tree, key);
    if (data) {
        printf("Read: File: %s, Offset: %zu, Length: %zu, Data: %.*s\n", fn, offset, size, (int)size, data);
    } else {
        printf("Read: File: %s, Offset: %zu, Length: %zu, Data not found\n", fn, offset, size);
    }
}

/**
 * @brief 主函数
 * 
 * 创建基数树，执行模拟的写操作和读操作。
 * 
 * @return int 程序正常结束返回0
 */
int main() {
    RadixTree *tree = create_tree();
    Mwrite(tree, "testfile", 0, "Hello, World!");
    Mread(tree, "testfile", 0, 13);
    Mread(tree, "testfile", 4096, 13);  ///< 这应当找不到数据
    return 0;
}
